翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Schröder-Bernstein theorem : ウィキペディア英語版
Schröder–Bernstein theorem
In set theory, the Schröder–Bernstein theorem, named after Felix Bernstein and Ernst Schröder, states that, if there exist injective functions and between the sets ''A'' and ''B'', then there exists a bijective function . In terms of the cardinality of the two sets, this means that if |''A''| ≤ |''B''| and |''B''| ≤ |''A''|, then |''A''| = |''B''|; that is, ''A'' and ''B'' are equipollent. This is a useful feature in the ordering of cardinal numbers.
The theorem is also known as the Cantor–Bernstein theorem, or the Cantor–Schroeder–Bernstein theorem (named after Georg Cantor).
This theorem does not rely on the axiom of choice. However, its various proofs are non-constructive, as they depend on the law of excluded middle, and are therefore rejected by intuitionists.
==Proof==

The following proof is attributed to Julius König.
Assume without loss of generality that ''A'' and ''B'' are disjoint. For any ''a'' in ''A'' or ''b'' in ''B'' we can form a unique two-sided sequence of elements that are alternately in ''A'' and ''B'', by repeatedly applying ''f'' and ''g'' to go right and ''g^'' and ''f^'' to go left (where defined).
:'' \cdots \rightarrow f^(g^(a)) \rightarrow g^(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots ''
For any particular ''a'', this sequence may terminate to the left or not, at a point where ''f^'' or ''g^'' is not defined.
By the fact that ''f'' and ''g'' are injective functions, each ''a'' in ''A'' and ''b'' in ''B'' is in exactly one such sequence to within identity: if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by the definition of the sequences. Therefore, the sequences form a partition of the (disjoint) union of ''A'' and ''B''. Hence it suffices to produce a bijection between the elements of ''A'' and ''B'' in each of the sequences separately, as follows:
Call a sequence an ''A-stopper'' if it stops at an element of ''A'', or a ''B-stopper'' if it stops at an element of ''B''. Otherwise, call it ''doubly infinite'' if all the elements are distinct or ''cyclic'' if it repeats. See the picture for examples.
* For an ''A-stopper'', the function ''f'' is a bijection between its elements in ''A'' and its elements in ''B''.
* For a ''B-stopper'', the function ''g'' is a bijection between its elements in ''B'' and its elements in ''A''.
* For a ''doubly infinite'' sequence or a ''cyclic'' sequence, either ''f'' or ''g'' will do (g is used in the picture).

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Schröder–Bernstein theorem」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.